/*
 * @Descripttion:
 * @Author: ziwei
 * @Date: 2022-12-13 10:48:40
 * @LastEditors: ziwei
 * @LastEditTime: 2022-12-13 15:54:21
 */
//1. 看最新的和尾部最后一项的关系，如果比他大直接放到后面
//2. 去列表中查找 比当前项大的做替换

//2 5 8 4 6 7 9 3
//2 5
//2 5 8
//2 4 8
//2 4 6
//2 4 6 7
//2 4 6 7 9
//2 3 6 7 9
//1 采用二分查找 + 贪心算法：永远认为后面一个大

//3 4 5 9 7 6

function getSequence(arr) {
  let len = arr.length;
  let result = [0]; //默认连续的最终结果 组成的索引
  let resultLastIndex;
  let start;
  let end;
  let middle;
  let p = arr.slice(0); //用来标识索引
  for (let i = 0; i < len; i++) {
    ////vue中序列中不会出现0 如果序列中出现0的话可以忽略
    const arrI = arr[i];
    if (arrI !== 0) {
      resultLastIndex = result[result.length - 1];
      if (arr[resultLastIndex] < arrI) {
        result.push(i);
        p[i] = resultLastIndex; //让当前最后一项记住前一项的索引
        continue;
      }

      //这里就会出现 当前项比后一项大的值 [0,1,2]
      start = 0;
      end = result.length - 1;
      while (start < end) {
        middle = ((start + end) / 2) | 0;
        if (arr[middle] < arrI) {
          start = middle + 1;
        } else {
          end = middle;
        }
      }
      //middle 就是第一个比当前大的值
      if (arrI < arr[result[end]]) {
        p[i] = result[start - 1]; //记住还的人的前面一项
        result[end] = i;
      }
    }
  }
  //追溯
  let i = result.length; //获取数组的长度
  let last = result[i - 1]; //在最后一项的索引
  while (i-- > 0) {
    result[i] = last; //用最后一项的索引来追溯
    last = p[last]; //用p中的索引来进行追溯
  }
  return result;
}
// 2 3 6 7 8
//[0,7,4,5,6]
// 2 4 6 7 9
let res = getSequence([2, 5, 8, 4, 6, 7, 9, 3]);
console.log(res);

//2 追溯
